package com.huang;

import java.util.Random;

/**
 * @author HuangShen
 * @Description 快速排序
 * @create 2021-03-21 16:08
 */
public class QuickSort {
    public static void main(String[] args) {

        int[] ints = creatData(100000000, 100000);
//        pData(ints);
        quickSort(ints);
//        pData(ints);

    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[j];
        data[j] = data[i];
        data[i] = temp;
    }


    private static void subSort(int[] data, int start, int end) {
        if (start < end) {
            int base = data[start];
            int heigh = end+1;
            int low = start;
            while (true) {
                while (low<end&&data[++low]>=base);
                while (heigh>start&&data[--heigh]<=base);
                if (low<heigh){
                    swap(data, low, heigh);
                }else {

                    break;
                }
            }
            swap(data, start, heigh);
            subSort(data, start, heigh - 1);
            subSort(data, heigh + 1, end);
        }
    }

    public static int [] quickSort(int [] data){
        long start = System.currentTimeMillis();
        subSort(data ,0,data.length-1);
        long end = System.currentTimeMillis();
        System.out.println("一共用时:"+(end-start));
        return data;
    }



    public static int [] creatData(int size,int max){
        int [] data=new int [size];
        for (int i = 0; i < size - 1; i++) {
            data[i]=new Random().nextInt(max);
        }
        return data;
    }

    public static void pData(int[] data){
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println();
    }



}
